package leetcode.editor.cn;

import leetcode.editor.cn.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
* @Author: Dempsey
* @Data: 2021-03-01 17:14:41
*/

//给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，
// 判断该树中是否存在 根节点到叶子节点 的路径，
// 这条路径上所有节点值相加等于目标和
// targetSum 。 
//
// 叶子节点 是指没有子节点的节点。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,3], targetSum = 5
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], targetSum = 0
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目在范围 [0, 5000] 内 
// -1000 <= Node.val <= 1000 
// -1000 <= targetSum <= 1000 
// 
// Related Topics 树 深度优先搜索 
// 👍 522 👎 0


public class P112{
	public static void main(String[] args) {
		Solution solution = new P112().new Solution();
	}
	
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
			if (root == null) {
				return false;
			}

			Queue<TreeNode> queue = new LinkedList<>();
			queue.offer(root);

			while (!queue.isEmpty()) {
				// 得这么写，因为 queue 的 size 一直在变
				int currentLevelSize = queue.size();
				for (int i = 0; i < currentLevelSize; i++) {
					TreeNode node = queue.poll();
					if (node.left != null) {
						node.left.val += node.val;
						queue.offer(node.left);
					}
					if (node.right != null) {
						node.right.val += node.val;
						queue.offer(node.right);
					}
					if (node.left ==null && node.right == null && node.val == targetSum) return true;
				}

			}

    	return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}